package com.buddy.learn.algorithm.exam;

/**
 * @author Buddy
 * @date 2021/6/9
 */
public class SolutionXM3 {


    /**
     * 有100只羊围成一圈，然后从中任意一只开始数1，2，3，
     * 到第三只的时候，牵出来，从下一只开始从头数，以此往复，
     * 直到只剩下一只为止。然后按照牵出顺序进行打印。
     *
     * @param args
     */
    public static void main(String[] args) {
        Node head = new Node(1, null);
        Node prev = head;
        Node tail = null;
        for (int i = 2; i <= 100; i++) {
            Node node = new Node(i, null);
            prev.setNext(node);
            prev = node;
            tail = node;
        }
        tail.setNext(head);
        Node curr = head;
        int i = 1;
        Node p = null;
        while (curr.getNext() != null && curr.getNext() != curr) {
            if (i == 3) {
                System.out.println(curr.getVal());
                Node n = curr.getNext();
                p.setNext(n);
                i = 0;
            } else {
                p = curr;
            }
            i++;
            curr = curr.getNext();
        }
        System.out.println(curr.getVal());
    }


}

class Node {
    private int val;
    private Node next;

    public Node(int val,  Node next) {
        this.val = val;
        this.next = next;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
